package com.lxl.bubble;

import java.util.Arrays;

/**
 * @Classname BubbleSort
 * @Description 冒泡排序
 * 重复地走访要排序的元素 依次比较两个相邻的元素 必要时进行交换
 * 走访元素的工作是重复地进行知道没有相邻元素需要交换 即该元素已经排序完成
 *
 * 时间复杂度：O(N^2)
 * 稳定
 *
 *
 * @Date 2021/8/11 10:11
 * @Created by LXLDEMO
 */
public class BubbleSort {

    public static void main(String[] args) {
        int arr[] = {2,4,3,1,6,5};

        // 普通冒泡排序测试
//        bubbleSort(arr,arr.length);

        //第一次优化
//        bubbleSortOptimize1(arr,arr.length);

        //第二次优化
        bubbleSortOptimize2(arr,arr.length);
    }

    /**
     * 普通冒泡排序
     * 缺陷：耗时 每次都会无条件遍历
     * @param arr
     * @param len arr.length
     */
    public static void bubbleSort(int arr[],int len){
        for (int i = 0;i<len-1;i++){
            System.out.println();
            System.out.println("第"+(i+1)+"轮");
            for (int j=0;j<len-1-i;j++){
                if (arr[j]>arr[j+1]){
                    // 交换
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
                System.out.println("第"+(i+1)+"_"+(j+1)+"交换：" + Arrays.toString(arr));
            }
        }
    }

    /**
     * 冒泡排序
     * 第一次优化：当第n次没有数据交换的时候 结束循环
     *
     * @param arr
     * @param len arr.length
     */
    public static void bubbleSortOptimize1(int arr[],int len){
        System.out.println("第一次优化：\n记录本轮循环是否发生了交换\n\n");

        boolean swap = true;
        for (int i = 0;i<len-1&&swap;i++){
            // 上一轮没有发生交换 表示已经排序好 跳出此层循环 （结束排序）
            if (!swap){
                break;
            }
            System.out.println("第"+(i+1)+"轮");

            swap = false;// 如果下面有数据交换的话 改为true
            for (int j=0;j<len-1-i;j++){
                if (arr[j]>arr[j+1]){
                    // 交换
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                    swap = true; // 这一轮发生了交换 表示数据可能没有排好
                }
                System.out.println("第"+(i+1)+"_"+(j+1)+"交换：" + Arrays.toString(arr));
            }
        }
    }

    /**
     * 冒泡排序
     * 第二次优化：记录最后交换的位置减少一轮中遍历次数 当第n次没有数据交换的时候 结束循环
     * @param arr
     * @param len arr.length
     */
    public static void bubbleSortOptimize2(int[] arr,int len){
        System.out.println("第二次优化：\n记录最后交换的位置减少一轮中遍历次数\n当第n次没有数据交换的时候 结束循环\n\n");
        // 记录是否需要交换
        boolean swap = true;
        int swappedIndex = -1;// 记录上次冒泡过程中发生交换的位置
        int lastIndex = len -1;// 定义内层循环条件：上一次最后发生交换的位置
        int i = 0;// 记录是第几次循环
        while(swap && lastIndex!=0){
            i++;
            System.out.println("第"+i+"轮");
            // 假定不需要交换
            swap = false;
            for (int j = 0;j<lastIndex;j++){
                if (arr[j]>arr[j+1]){
//                    int temp = arr[j];
//                    arr[j] = arr[j+1];
//                    arr[j+1] = temp;
                    swap(arr,j,j+1);
                    swap = true;
                    swappedIndex = j;
                }
                System.out.println("第"+i+"_"+(j+1)+"交换：" + Arrays.toString(arr));
            }
            lastIndex = swappedIndex;
            System.out.println("最后交换的位置："+lastIndex+"\n");
        }
    }

    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}
